// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

// phiopt消除了基于前一个if的布尔PHI。
// None
// 主要用例是转换：
// x:=假
// 如果b{
// x=真
// }
// 变成x=b。
// None
// 在SSA代码中，这显示为
// None
// b0
// 如果b->b1和b2
// b1
// 普通->b2
// b2
// x=（OpPhi（ConstBool[true]）（ConstBool[false]））
// None
// 在这种情况下，我们可以用b的副本替换x。
func phiopt(f *Func) {
	sdom := f.Sdom()
	for _, b := range f.Blocks {
		if len(b.Preds) != 2 || len(b.Values) == 0 {
			// 待办事项：处理两个以上的前辈，例如a | | b | | c。
			continue
		}

		pb0, b0 := b, b.Preds[0].b
		for len(b0.Succs) == 1 && len(b0.Preds) == 1 {
			pb0, b0 = b0, b0.Preds[0].b
		}
		if b0.Kind != BlockIf {
			continue
		}
		pb1, b1 := b, b.Preds[1].b
		for len(b1.Succs) == 1 && len(b1.Preds) == 1 {
			pb1, b1 = b1, b1.Preds[0].b
		}
		if b1 != b0 {
			continue
		}
		// b0是给出布尔值的if块。
		// 反向是真理值的前身。
		var reverse int
		if b0.Succs[0].b == pb0 && b0.Succs[1].b == pb1 {
			reverse = 0
		} else if b0.Succs[0].b == pb1 && b0.Succs[1].b == pb0 {
			reverse = 1
		} else {
			b.Fatalf("invalid predecessors\n")
		}

		for _, v := range b.Values {
			if v.Op != OpPhi {
				continue
			}

			// 查找从布尔到0/1的转换。
			if v.Type.IsInteger() {
				phioptint(v, b0, reverse)
			}

			if !v.Type.IsBoolean() {
				continue
			}

			// 取代
			// 如果a{x=true}否则{x=false}与x=a
			// 和
			// 如果a{x=false}否则{x=true}与x=！A.
			if v.Args[0].Op == OpConstBool && v.Args[1].Op == OpConstBool {
				if v.Args[reverse].AuxInt != v.Args[1-reverse].AuxInt {
					ops := [2]Op{OpNot, OpCopy}
					v.reset(ops[v.Args[reverse].AuxInt])
					v.AddArg(b0.Controls[0])
					if f.pass.debug > 0 {
						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
					}
					continue
				}
			}

			// 取代
			// 如果a{x=true}否则{x=value}为x=a | |值。
			// 要求该值支配x，这意味着无论a如何，
			// 值始终是计算出来的。这保证了副作用
			// 如果a为false，则看不到值的。
			if v.Args[reverse].Op == OpConstBool && v.Args[reverse].AuxInt == 1 {
				if tmp := v.Args[1-reverse]; sdom.IsAncestorEq(tmp.Block, b) {
					v.reset(OpOrB)
					v.SetArgs2(b0.Controls[0], tmp)
					if f.pass.debug > 0 {
						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
					}
					continue
				}
			}

			// 取代
			// 如果一个{x=value}或者{x=false}为x=a&&value。
			// 要求该值支配x，这意味着无论a如何，
			// 值始终是计算出来的。这保证了副作用
			// 如果a为false，则看不到值的。
			if v.Args[1-reverse].Op == OpConstBool && v.Args[1-reverse].AuxInt == 0 {
				if tmp := v.Args[reverse]; sdom.IsAncestorEq(tmp.Block, b) {
					v.reset(OpAndB)
					v.SetArgs2(b0.Controls[0], tmp)
					if f.pass.debug > 0 {
						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
					}
					continue
				}
			}
		}
	}
	// 加强phi优化。
	// 主要用例是转换：
	// x:=假
	// 如果c{
	// x=真
	// ...
	// }
	// 进入
	// x:=c
	// 如果x{…}
	// None
	// 例如，在SSA代码中，案例显示为
	// b0
	// 如果c->b，sb0
	// sb0
	// 如果d->sd0，sd1
	// sd1
	// ...
	// sd0
	// 普通->b
	// B
	// x=（OpPhi（ConstBool[true]）（ConstBool[false]））
	// None
	// 在这种情况下，我们也可以用c的副本替换x。
	// None
	// 优化理念：
	// 1.块b具有φ值x，x=OpPhi（ConstBool[true]）（ConstBool[false]），
	// len（b.Preds）等于2。
	// 2.找到块b的前辈（pb0，pb1）的共同支配者（b0），以及
	// 支配符（b0）是一个If块。
	// 特例：其中一个前辈（pb0或pb1）是支配者（b0）。
	// 3.支配者的继任者（sb0，sb1）需要支配前任者（pb0，pb1）
	// 分别位于b区。
	// 4.替换此基于支配块的布尔φ。
	// None
	// b0（pb0）b0（pb1）b0
	// |  \               /  |             /  \
	// |sb1 sb0 | sb0 sb1
	// |  ...           ...  |           ...   ...
	// |pb1 pb0 | pb0 pb1
	// |  /               \  |            \   /
	// b b b
	// None
	var lca *lcaRange
	for _, b := range f.Blocks {
		if len(b.Preds) != 2 || len(b.Values) == 0 {
			// 待办事项：处理两个以上的前辈，例如a | | b | | c。
			continue
		}

		for _, v := range b.Values {
			// 查找phi值v=OpPhi（ConstBool[true]）（ConstBool[false]）。
			// TODO:v=OpPhi（ConstBool[true]）（Arg<bool>{value}）
			if v.Op != OpPhi {
				continue
			}
			if v.Args[0].Op != OpConstBool || v.Args[1].Op != OpConstBool {
				continue
			}
			if v.Args[0].AuxInt == v.Args[1].AuxInt {
				continue
			}

			pb0 := b.Preds[0].b
			pb1 := b.Preds[1].b
			if pb0.Kind == BlockIf && pb0 == sdom.Parent(b) {
				// 特殊情况：pb0是控制块b0。
				// b0（pb0）
				// |  \
				// |sb1
				// |  ...
				// |pb1
				// |  /
				// B
				// 如果b0（pb0）的另一个后继sb1支配pb1，则更换。
				ei := b.Preds[0].i
				sb1 := pb0.Succs[1-ei].b
				if sdom.IsAncestorEq(sb1, pb1) {
					convertPhi(pb0, v, ei)
					break
				}
			} else if pb1.Kind == BlockIf && pb1 == sdom.Parent(b) {
				// 特殊情况：pb1是控制块b0。
				// b0（pb1）
				// /   |
				// sb0|
				// ...  |
				// pb0|
				// \  |
				// B
				// 如果b0（pb0）的另一个后继sb0支配pb0，则更换。
				ei := b.Preds[1].i
				sb0 := pb1.Succs[1-ei].b
				if sdom.IsAncestorEq(sb0, pb0) {
					convertPhi(pb1, v, 1-ei)
					break
				}
			} else {
				// b0
				// /   \
				// sb0 sb1
				// ...  ...
				// pb0-pb1
				// \   /
				// B
				// None
				// 为最不常见的快速祖先查询构建数据结构。
				if lca == nil {
					lca = makeLCArange(f)
				}
				b0 := lca.find(pb0, pb1)
				if b0.Kind != BlockIf {
					break
				}
				sb0 := b0.Succs[0].b
				sb1 := b0.Succs[1].b
				var reverse int
				if sdom.IsAncestorEq(sb0, pb0) && sdom.IsAncestorEq(sb1, pb1) {
					reverse = 0
				} else if sdom.IsAncestorEq(sb1, pb0) && sdom.IsAncestorEq(sb0, pb1) {
					reverse = 1
				} else {
					break
				}
				if len(sb0.Preds) != 1 || len(sb1.Preds) != 1 {
					// 在以下情况下，我们不能替换φ值x。
					// 如果gp==nil | | sp<lo{x=true}
					// 如果a | | b{x=true}
					// 因此if语句只能有一个条件。
					break
				}
				convertPhi(b0, v, reverse)
			}
		}
	}
}

func phioptint(v *Value, b0 *Block, reverse int) {
	a0 := v.Args[0]
	a1 := v.Args[1]
	if a0.Op != a1.Op {
		return
	}

	switch a0.Op {
	case OpConst8, OpConst16, OpConst32, OpConst64:
	default:
		return
	}

	negate := false
	switch {
	case a0.AuxInt == 0 && a1.AuxInt == 1:
		negate = true
	case a0.AuxInt == 1 && a1.AuxInt == 0:
	default:
		return
	}

	if reverse == 1 {
		negate = !negate
	}

	a := b0.Controls[0]
	if negate {
		a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
	}
	v.AddArg(a)

	cvt := v.Block.NewValue1(v.Pos, OpCvtBoolToUint8, v.Block.Func.Config.Types.UInt8, a)
	switch v.Type.Size() {
	case 1:
		v.reset(OpCopy)
	case 2:
		v.reset(OpZeroExt8to16)
	case 4:
		v.reset(OpZeroExt8to32)
	case 8:
		v.reset(OpZeroExt8to64)
	default:
		v.Fatalf("bad int size %d", v.Type.Size())
	}
	v.AddArg(cvt)

	f := b0.Func
	if f.pass.debug > 0 {
		f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
	}
}

// b是给出布尔值的If块。
// v是phi值v=（OpPhi（ConstBool[true]）（ConstBool[false]）。
// 反向是真理值的前身。
func convertPhi(b *Block, v *Value, reverse int) {
	f := b.Func
	ops := [2]Op{OpNot, OpCopy}
	v.reset(ops[v.Args[reverse].AuxInt])
	v.AddArg(b.Controls[0])
	if f.pass.debug > 0 {
		f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
	}
}
